import java.util.NoSuchElementException;

/**
 * A heap tha maintains the root at position 1
 * @author Matt Dye
 *
 */
public class Heap<T extends Comparable<T>> implements PriorityQueue<T> {
	private T[] array;
	private int size;
	
	@SuppressWarnings("unchecked")
	public Heap(int capacity)
	{
		array = (T[]) new Comparable[capacity + 1];
		size = 0;
	}
	
	public Heap()
	{
		this(10);
	}
	
	
	/**
	 * Adds an element to the priority queue.
	 * 
	 * @param element
	 *            The element to add
	 * @throws NullPointerException
	 *             If element is null
	 */
	
	public void add(T element)
	{
		if(element == null)
			throw new  NullPointerException();
		size++;
		int i = size;
		if(size > array.length)
		{
			@SuppressWarnings("unchecked")
			T []newArray = (T[]) new Comparable[2 * array.length + 1];
			for(int j = 1; j <= size;j++)
			{
				newArray[j] = array[j];
			}
			array = newArray;
		}
		array[size] = element;
		while(i != 1 && array[i].compareTo(array[i/2]) < 0)
		{
		   swap(i,i/2);
		   i = i/2;
		}

	}

	/**
	 * Removes the minimum element in the priority queue.
	 * 
	 * @return The minimum element in the priority queue
	 * @throws NoSuchElementException
	 *             If the priority queue is empty
	 */
	public T remove()
	{
		T out = null;
		if(size == 0)
			throw new NoSuchElementException();
		else
		{
		 out = array[1];
		array[1] = array[size];
		array[size] = null;
		size--;
		heapify(1);
		}
		return out;
		
	}

	/**
	 * Returns, but does not remove, the minimum element in the priority queue.
	 * 
	 * @return The minimum element in the priority queue
	 */
	public T peek()
	{
		return array[1];
	}

	/**
	 * Determines if the priority queue is empty.
	 * 
	 * @return true if the priority queue is empty, or false otherwise
	 */
	public boolean isEmpty()
	{
		return size==0;
	}

	/**
	 * Empties the priority queue.
	 */
	@SuppressWarnings("unchecked")
	public void clear()
	{
		array = (T[]) new Object[10];
		size = 0;
	}

	/**
	 * Returns the number of elements in the priority queue.
	 * 
	 * @return The size of the priority queue
	 */
	public int size()
	{
		return size;
	}
	/**
	 * Heapify will go through the array to make it match the priority queue requirements
	 * @param index Where to start
	 */
	public void heapify(int index)
	{
		T min = array[index];
		if(index>=size)
			{
				
			}
		else if(array[2*index] != null && array[2*index].compareTo(min)<0)
			{
				if(array[2*index+1] != null && array[2*index+1].compareTo(array[index+1])<0)
				{
					min = array[2*index+1];
					swap(index,2*index+1);
					heapify(2*index+1);
				}
				else
				{
					min = array[2*index];
					swap(index,2*index);
					heapify(2*index);
				}
			}
		else if(array[2*index+1] != null && array[2*index+1].compareTo(min)<0)
			{
				min = array[2*index+1];
				swap(index,2*index+1);
				heapify(2*index+1);
			}
	}
	@Override
	public String toString()
	{
		int semiIndex = 2;
		String out = "";
		for(int i = 1; i<= size; i++)
		{
			if(i+1 == semiIndex)
			{
				out = out + array[i] + ";";
				semiIndex = semiIndex * 2;
			}
			else
			{
				out = out + array[i].toString();
			}
		}
		return out;
			
	}
	

	public T[] getArray() {
		return array;
	}

	public void setArray(T[] array) {
		this.array = array;
	}

	public int getSize() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}
/**
 * Swaps 2 items in the current arrray
 * @param ind1
 * @param ind2
 */
	public void swap(int ind1, int ind2)
	{
		T temp = array[ind1];
		array[ind1] = array[ind2];
		array[ind2] = temp;
	}
	

}
